package com.hdu.hot100.tree;

public class lc108 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return build(nums, 0, nums.length - 1);
        }

        TreeNode build(int[] nums, int l, int r) {
            if (l > r) return null;
            else if (l == r) return new TreeNode(nums[l]);
            else {
                int mid = l + ((r - l) >> 1);
                TreeNode root = new TreeNode(nums[mid]);
                root.left = build(nums, l, mid - 1);
                root.right = build(nums, mid + 1, r);
                return root;
            }
        }
    }
}
